package com.ljy.my_study.leetcode.乘积最大子数组;

/**
 * @author lijunying
 * @date 2021/11/26 11:35
 */
public class TestMain {

//    给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
//
//             
//
//    示例 1:
//
//    输入: [2,3,-2,4]
//    输出: 6
//    解释: 子数组 [2,3] 有最大乘积 6。
//    示例 2:
//
//    输入: [-2,0,-1]
//    输出: 0
//    解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/maximum-product-subarray
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        int[] nums={2,3,-2,4};
        System.out.println(new TestMain().maxProduct(nums));
    }

//    动态规划
    public int maxProduct(int[] nums) {
        if(nums==null||nums.length==0){
            return Integer.MIN_VALUE;
        }
        int result=nums[0];
        int len=nums.length;
        int minF=nums[0];
        int maxF=nums[0];
        for(int i=1;i<len;i++){
            int min=minF,max=maxF;
            minF=Math.min(min*nums[i],Math.min(nums[i],max*nums[i]));
            maxF=Math.max(max*nums[i],Math.max(nums[i],min*nums[i]));
            result=Math.max(result,maxF);
        }
        return result;
    }
}
